# @Time    : 2025/1/2 10:49
# @Author  : Zhang Yihao
class Node:
    def __init__(self,elem=-1,lchild=None,rchild=None):
        self.elem=elem
        self.lchild=lchild
        self.rchild=rchild

class BinaryTree:
    def __init__(self):
        self.root=None
        self.help_queue=[]#辅助队列,存储节点

    def level_build_tree(self,node:Node):
        if self.root is None:
            self.root=node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if  self.help_queue[0].lchild is None:#左子树为空
                self.help_queue[0].lchild=node #放入左孩子
            else:
                self.help_queue[0].rchild=node #放入右孩子
                del self.help_queue[0]
                # self.help_queue.pop(0)

    # 先序遍历,深度优先遍历
    def pre_order(self,node:Node):
        if node is None:
            return
        print(node.elem,end=' ')
        self.pre_order(node.lchild)
        self.pre_order(node.rchild)

    def in_order(self,node:Node):
        if node is None:
            return
        self.in_order(node.lchild)
        print(node.elem,end=' ')
        self.in_order(node.rchild)

    def post_order(self,node:Node):
        if node is None:
            return
        self.post_order(node.lchild)
        self.post_order(node.rchild)
        print(node.elem,end=' ')

    # 广度优先遍历,层序遍历
    def level_order(self,node:Node):
        help_queue=[]
        help_queue.append(self.root)
        while help_queue:
            node=help_queue.pop(0)
            print(node.elem,end=' ')
            if node.lchild is not None:
                help_queue.append(node.lchild)
            if node.rchild is not None:
                help_queue.append(node.rchild)

if __name__ == '__main__':
    tree=BinaryTree()
    for i in range(1,11):
        new_node=Node(i)
        tree.level_build_tree(new_node)
    tree.pre_order(tree.root)
    print()
    tree.in_order(tree.root)
    print()
    tree.post_order(tree.root)
    print()
    tree.level_order(tree.root)